from typing import *


class Solution:

    def equalPairs(self, grid: List[List[int]]) -> int:
        n = len(grid)

        def f(i, j):
            for k in range(n):
                if grid[i][k] != grid[k][j]:
                    return 0
            return 1

        ans = 0
        for i in range(n):
            for j in range(n):
                ans += f(i, j)
        return ans


class Solution:

    def equalPairs(self, grid: List[List[int]]) -> int:
        n = len(grid)

        mod = 1000000007
        dd = DefaultDict(int)
        for i in range(n):
            h = 0
            for j in range(n):
                h += grid[i][j]
                h *= 100007
                h %= mod
            dd[h] += 1
        ans = 0
        for i in range(n):
            h = 0
            for j in range(n):
                h += grid[j][i]
                h *= 100007
                h %= mod
            ans += dd[h]
        return ans


class Solution:

    def equalPairs(self, grid: List[List[int]]) -> int:
        res, n = 0, len(grid)
        cnt = Counter(tuple(row) for row in grid)
        res = 0
        for j in range(n):
            res += cnt[tuple([grid[i][j] for i in range(n)])]
        return res


# 作者：LeetCode-Solution
# 链接：https://leetcode.cn/problems/equal-row-and-column-pairs/solution/xiang-deng-xing-lie-dui-by-leetcode-solu-gvcg/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。